#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

int lengthOfLIS(vector<int>& nums) {
	vector<int> dp(nums.size(), 1);
	for (int i = 1; i<nums.size(); i++)
	{
		for (int j = i; j >= 0; j--)
		{
			if (nums[i]>nums[j])
			{
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
	}
	sort(dp.begin(), dp.end());
	return dp[nums.size() - 1];
}

int findLengthOfLCIS(vector<int>& nums) {
	vector<int> dp(nums.size(), 1);
	for (int i = 1; i<nums.size(); i++)
	{
		if (nums[i - 1]<nums[i])
		{
			dp[i] = dp[i - 1] + 1;
		}
	}
	sort(dp.begin(), dp.end());
	return dp[nums.size() - 1];
}

int findLength(vector<int>& nums1, vector<int>& nums2) {
	vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
	int count = INT_MIN;
	for (int i = 1; i <= nums1.size(); i++)
	{
		for (int j = 1; j <= nums2.size(); j++)
		{
			if (nums1[i - 1] == nums2[j - 1])
			{
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			count = max(count, dp[i][j]);
		}
	}
	return count;
}

int longestCommonSubsequence(string text1, string text2) {
	vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
	for (int i = 1; i <= text1.size(); i++)
	{
		for (int j = 1; j <= text2.size(); j++)
		{
			if (text1[i - 1] == text2[j - 1])
			{
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else
			{
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}
	return dp[text1.size()][text2.size()];
}


int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
	vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
	for (int i = 1; i <= nums1.size(); i++)
	{
		for (int j = 1; j <= nums2.size(); j++)
		{
			if (nums1[i - 1] == nums2[j - 1])
			{
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else
			{
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}
	return dp[nums1.size()][nums2.size()];
}

bool isSubsequence1(string s, string t) {
	vector<vector<int>> dp(t.size() + 1, vector<int>(s.size() + 1, 0));
	for (int i = 1; i <= t.size(); i++)
	{
		for (int j = 1; j <= s.size(); j++)
		{
			if (t[i - 1] == s[j - 1])
			{
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else
			{
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}
	return dp[t.size()][s.size()] == s.size();
}

bool isSubsequence(string s, string t) {
	vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
	for (int i = 1; i <= s.size(); i++) {
		for (int j = 1; j <= t.size(); j++) {
			if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
			else dp[i][j] = dp[i][j - 1];
		}
	}
	if (dp[s.size()][t.size()] == s.size()) return true;
	return false;
}


int numDistinct(string s, string t) {
	vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
	for (int i = 0; i<s.size(); i++)
	{
		dp[i][0] = 1;
	}
	for (int i = 1; i <= s.size(); i++)
	{
		for (int j = 1; j <= t.size(); j++)
		{
			if (s[i - 1] == t[j - 1])
			{
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
			}
			else
			{
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	for (int i = 0; i <= s.size(); i++)
	{
		for (int j = 0; j <= t.size(); j++)
		{
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}
	return dp[s.size()][t.size()];
}

int main()
{
	vector<int> arr1{ 1, 4, 2 };
	vector<int> arr2{ 1, 2, 4 };
	string s1 = "rabbbit";
	string s2 = "rabbit";
	cout << numDistinct(s1, s2) << endl;
	return 0;
}